package algorithm.sorting.compare.insertsort;

import algorithm.sorting.ISort;

/**
 * @author lancyguy
 * @author cgzh@hotmail.com
 * @param <T> type of the elements to be sorted
 */
public class InsertSorter<T extends Comparable<T>> implements ISort<T> {
    public InsertSorter(){

    }
    /**
     * sort the whole array
     * @param arr array to be sorted
     */
	public void sort(T[] arr) {
		sort(arr,0,arr.length-1);
	}

    /**
     * @param arr array to be sorted
     * @param head left boundary of the range of the array within which the sorting takes place
     * @param end  right boundary of the range of the array within which the sorting takes place.
     */
	public void sort(T[] arr, int head, int end) {
		if(arr.length==0 || head<0 || end>=arr.length || end-head<=0) 
    		return;
		for (int currentIndex=head+1;currentIndex<=end;currentIndex++) {
			T current = arr[currentIndex];
			int idx = currentIndex-1;
			while(idx>=head && current.compareTo(arr[idx])<0){
				arr[idx+1] = arr[idx];
				idx--;
			}
			arr[idx+1] = current;
		}
	}
}
